With a rapid development of information processing technology and communication technology, digitisation of documents, official and private, is rapidly advancing. Accordingly, many individuals and companies are greatly interested in security management of electronic documents. With the increase in the interest, security against tampering, such as eavesdropping and forgery of electronic documents, has come to be hotly debated in many fields. The security against eavesdropping on an electronic document is ensured by encrypting the electronic document, for example. Also, the security against forgery of an electronic document is ensured by using a digital signature, for example. However, encryption and the digital signature have to be sufficiently tamper-resistant.
The digital signature is used for specifying the author of an electronic document. Accordingly, the digital signature should be able to be generated only by the author of the electronic document. If a malicious third party is able to generate the same digital signature, such third party can impersonate the author of the electronic document. That is, an electronic document is forged by the malicious third party. Various opinions have been expressed regarding the security of the digital signature to prevent such forgery. As digital signature schemes that are currently widely used, schemes that use a RSA signature scheme and a DSA signature scheme are known, for example.
The RSA signature scheme takes “difficulty of prime factorisation of a large composite number (hereinafter, prime factorisation problem)” as a basis for security. Also, the DSA signature scheme takes “difficulty of solving discrete logarithm problem” as a basis for security. These bases are based on that algorithms that efficiently solve the prime factorisation problem and the discrete logarithm problem by using a classical computer do not exist. That is, the difficulties mentioned above suggest the computational difficulty of a classical computer. However, it is said that solutions to the prime factorisation problem and the discrete logarithm problem can be efficiently calculated when a quantum computer is used.
Similarly to the RSA signature scheme and the DSA signature scheme, many of the digital signature schemes and public key authentication schemes that are currently used also take difficulty of the prime factorisation problem or the discrete logarithm problem as a basis for security. Thus, if the quantum computer is put to practical use, security of such digital signature schemes and public key authentication schemes will not be ensured. Accordingly, new digital signature schemes and public key authentication schemes are desired that take as a basis for security a problem different from problems such as the prime factorisation problem and the discrete logarithm problem that can be easily solved by the quantum computer. As a problem which is not easily solved by the quantum computer, there is a difficulty of solving a multivariate polynomial (hereinafter, multivariate polynomial problem), for example.
Other problems that are thought to be difficult to solve by the quantum computer include the Syndrome Decoding problem, the Constrained Linear Equation problem, the Permuted Kernel problem, the Permuted Perception problem, the section-finding problem on an algebraic surface, and the like.
Among these problems, problems other than the section-finding problem on an algebraic surface are known to be NP-hard. As their applications, for example, non-patent literature 1, and non-patent literature 2 mentioned below disclose public key authentication schemes based on the Syndrome Decoding problem. Furthermore, non-patent literature 3 mentioned below discloses a public key authentication scheme based on the Permuted Kernel problem. Other than these, a public key authentication scheme based on the Constrained Linear Equations problem, a public key authentication scheme based on the Permuted Perceptions problem, and the like are also proposed.